This invention relates to digital telecommunications and signal processing and more particular to digital techniques for performing operations on elements in finite fields. Division of finite field elements in a Galois field, a particular type of finite field, is needed in many applications including algebraic decoding of block codes used in digital communications. A specific example is the calculation of error values in a Reed-Solomon decoder.
Operations on finite field GF(q.sup.m) elements, such as division of one element by another element, are known in the prior art. Division can be done by finding the inverse of the divisor and multiplying the inverse by the dividend. One circuit for inverting a finite field element contains a pre-computed inverse for each field element, stored in a Read Only Memory (ROM). Another circuit implements a recursive inverter using a variation of Euclid's algorithm. The inverse computation using a ROM is suggested in Kuang Yung Lin, "Architecture for VLSI Design of Reed-Solomon Decoders", IEEE Transactions on Computers, Vol. C-33, No. 2, pp. 178-89 (Feb. 1984), and in I. S. Hsu et al., "The Design Plan of a VLSI Single Chip (255, 223) Reed-Solomon Decoder", TDA Progress Report 42-91, Jet Propulsion Laboratory, Pasadena, Calif., pp. 186-99 (July-Sept 1987). A recursive inverter using Euclid's algorithm for finding the inverse of a finite field element is shown in Berlekamp, Algebraic Coding Theory, pp. 36-44 (McGraw-Hill, 1968).
The ROM circuit can handle faster data rates since the ROM circuit can provide an inverse element one clock cycle after receiving an element, but the complexity of such a ROM circuit grows exponentially with m, the dimension of the finite field. A recursive inverter requires 2m clock cycles to complete the inverse calculation, but the circuit's complexity only grows linearly with m.
The recursive inverter using Euclid's algorithm for finding the inverse of an element in a finite field GF(q.sup.m) works as follows. Let p(x) be a primitive polynomial of the finite field GF(q.sup.m), b(x) be an element in GF(q.sup.m) , and w(x) be the inverse of b(x), where b(x).noteq.0, EQU p(x)=p.sub.0 +p.sub.1 x+. . . +p.sub.m x.sup.m, (1) EQU b(x)=b.sub.0 +. . . +b.sub.m-1 x.sup.m-1, (2) ##EQU1## and where {b.sub.i }, {p.sub.i } are elements of the base field GF(q). Euclid's algorithm for finding w(x) is described by the following recursion:
Step 0: (initial conditions) EQU w.sub.-1 (x)=0, w.sub.0 (x)=1, r.sub.-1 (x)=p(x), r.sub.0 (x)=b(x) (4) PA1 Step i, for i&gt;0: ##EQU2##
The [] notation in the above equations denotes polynomial functions which are related in the following manner: for an independent variable z and a polynomial function of z, f (z), the expression EQU [f(z)].sub..alpha..sup..beta. ( 7)
denotes the polynomial function, g(z), where g(z) is defined as having the same coefficients as f(z) for powers from z.sup..alpha. to z.sup..beta., and coefficients of zero for all other powers of z. For example, the [] notation in Equations 5 and 6, where the range of coefficients is from zero to positive infinity, denotes the nonnegative integer powers of x in the function r.sub.i-2 (x)/r.sub.i-1 (x). Thus, the above-described Euclid's algorithm repeatedly divides a remainder by a quotient to arrive at a remainder, where at each step, the remainder is a polynomial of lower degree than the previous remainder, until r.sub.i (x)=1. When r.sub.i (x)=1, w.sub.i (x)=1/b(x), or w(x).
After producing w(x), the circuit must then provide w(x) to a multiplier circuit. For example, if a(x) is to be divided by b(x) to find quotient c(x), w(x) and a(x) are provided to the inputs of a multiplier circuit to arrive at c(x), since c(x)=a(x)/b(x) mod p(x) implies c(x)=a(x)*w(x) mod p(x). Since c(x) is also an element of GF(q.sup.m), an implied modulo p(x) operation is provided as part of the multiplier.
Finite field manipulation circuits are often used in communications systems where a continuous stream of data is supplied as an input. Finite field manipulation circuits may also be used in encryption subsystems, which are also often used in communications systems. Because of the continuous stream of data, each finite field manipulation circuit must be dedicated to a single operation, or else a delay is introduced by any multiple purpose circuits as they perform their many functions serially. Due to the many manipulations on the signal, such as inversion, multiplication, decoding and the like, and particularly where data encryption is involved, the amount of circuitry is large, and any means to eliminate operations, especially in an integrated circuit where space for circuitry is always a concern, will make designs of systems simpler, faster, less expensive and thus more attractive to use than other alternatives.